第十二天 Process Synchronization(同步)--中

今天來說說critical section problem的解決方法：

• Peterson’s solution：
  他是一種軟體的方式解決critical section problem，假設有兩個process不可中斷，共享兩個變數：
  int turn代表誰能夠進入critical section
  Boolean flag[2]代表誰準備好了
  以下有舉例(同時會有兩組程式碼在執行，一個process i一個process j)：
  
  在上面的案例中，他遵守著昨天所提到的三個條件：

  1. Mutual Exclusion(互斥)：
     如果Pi要執行，那flag[j]=false或是turn=i (這代表j不想執行，或是優先權在i的手上)
  2. Progress(前進)：
     以Pj要執行為前提，有三種情況可能發生：
  • Pi不想執行Pj直接進入
  • Pi、Pj同時想執行，優先權在i的手上，Pi先執行
  • Pi、Pj同時想執行，優先權在j的手上，Pj先執行
  3. Bounded Waiting(有限等待)：
     當Pi執行完後又想執行，但這時Pj也想執行，這時優先權在j的手上，所以Pj先執行(Pi最多等一次就可以進去)

• Synchronization hardware

  他是一種硬體的方式解決critical section problem，用lock的方式保護critical section。現在主要用不可中斷的方式達到lock的功能，主要使用兩種方式：test memory word and set value(測試跟設值) 跟swap contents of two memory words(內容交換)

  1. test memory word and set value：
     把值寫到一個新的地方，回傳舊值
     test_and_set Instruction不會被中斷，以下是他的定義：
     
     接下是是解決方式的程式碼：
     
     lock是共享的變數，當執行test_and_set(&lock)，會將lock變數記憶體的位置傳入test_and_set()這時會被上所，等執行完後lock才會被解鎖。
  2. swap contents of two memory words：
     compare_and_swap instruction不可被中斷，以下是他的定義：
     
     接下來是解決方式的程式碼：
     
     lock是共享變數，初始值為0 (0代表不能進去，1代表可以進去)，當執行compare_and_swap(&lock , 0 , 1)，會去比對lock跟expected的值，如果相同就會把值做交換。

• Mutex Locks：
  這是一種programmer可以用的方式，利用acquire()和release()取用lock，但是如果取不到lock的話，就會進入busy waiting。以下是用法：
  

• Semaphore：
  這也是一種programmer可以用的方式，他是一個介於0到指定最大值的整數變數。利用wait()和signal()來改變，當執行完wait()則減1，而執行完signal()則加1。當變數等於0時，就要等到執行完signal()才能再執行wait()。

  當執行時，不能同時有兩個process執行wait()和signal()，也就是把wait()和signal()放入critical section，但這樣就有可能產生busy waiting。為了不要有busy waiting，會將所有的semaphore(有value跟pointer)連成一個waiting queue。而waiting queue有兩種執行方式：block(process放入waiting queue)跟wakeup(process移出waiting queue，放入ready queue)。

這裡我們先小提一下deadlock跟starvation，deadlock就是兩個process互相在等待對方佔著的資源; starvation就是一個process永遠等不到使用資源，就這樣被放著。還有一個Priority Inversion，就是高priority要用的資源被低priority鎖住，這時就要用priority-inheritance protocol來解決。

剩下的我們明天繼續～～